import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=131 lang=java
 *
 * [131] 分割回文串
 */

// @lc code=start
class Solution {
    List<List<String>> res=new ArrayList<>();
    LinkedList<String> path=new LinkedList<>();
    public List<List<String>> partition(String s) {
        dfs(s, 0);
        return res;
    }
    public void dfs(String s,int startIndex){
        if(startIndex>=s.length()){
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=startIndex;i<s.length();i++){
            String temp=s.substring(startIndex, i+1);//注意细节，substring是左闭右开截取子串
            if(needed(temp)){
                path.add(temp);
                dfs(s, i+1);
                path.removeLast();
            }
        }
    }
    
    private boolean needed(String temp) {
        for(int i=0,j=temp.length()-1;i<=j;i++,j--){
            if(temp.charAt(i)!=temp.charAt(j)){
                return false;
            }
        }
        return true;
    }
}
// @lc code=end

